# 什么是算法分析

# 程序是物理层面， 算法是逻辑层面
# 运行时间检测法

# 大O表示法
# 赋值语句是一个合适的选择，

# 分析SumOfN的赋值语句执行次数
import time

def SumOfN(n):
    theSum = 0
    for i in range(1, n+1):
        theSum += 1
    return theSum

# 问题规模：n
# 赋值语句T(n) = 1+n
# theSum 先执行了一次
# 然后for循环执行了n次，

# 数量级函数O(f(n))
 
# 逐一比较法 
def anagramSolution(s1, s2):
    alist = list(s2)
    pos1 = 0
    stillOk = True
    while pos1 < len(s1) and stillOk:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:
                found = True
            else:
                pos2 += 1
        if found:
            alist[pos2] = None
        else:
            stillOk = False
        pos1 += 1
    return stillOk

print(anagramSolution('abcdefghijklmnopkrrrrrrrrrrrrrrrrrst', 'adc'))

start1 = time.time()
print(anagramSolution('abcdefghijklmnopkrrrrrrrrrrrrrrrrrst', 'abcdefghijklmnopkrrrrrrrrrrrrrrrrrst'))
delta1 = time.time() - start1

# 排序比较法
def anagramSolution1(s1, s2):
    alist1 = list(s1)
    alist2 = list(s2)
    
    alist1.sort()
    alist2.sort()
    pos = 0
    matches = True
    while pos < len(s1) and matches:
        if alist1[pos] == alist2[pos]:
            pos += 1
        else:
            matches = False
    return matches

# 算法复杂度：O(n log n)

print(anagramSolution1('abcdefghijklmnopkrrrrrrrrrrrrrrrrrst', 'adc'))
start2 = time.time()
print(anagramSolution1('abcdefghijklmnopkrrrrrrrrrrrrrrrrrst', 'abcdefghijklmnopkrrrrrrrrrrrrrrrrrst'))
delta2 = time.time() - start2

# 计数比较
def anagrams(s1, s2):
    c1 = [0] * 26
    c2 = [0] * 26
    for i in range(len(s1)):
        pos = ord(s1[i]) - ord('a')
        c1[pos] = c1[pos] + 1
    for i in range(len(s2)):
        pos = ord(s2[i]) - ord('a')
        c2[pos] = c2[pos] + 1
    j = 0
    stillok = True
    while j < 26 and stillok:
        if c1[j] == c2[j]:
            j += 1
        else:
            stillok = False
    return stillok

print(anagrams('abcdefghijklmnopkrrrrrrrrrrrrrrrrrst', 'adc'))
start3 = time.time()
print(anagrams('abcdefghijklmnopkrrrrrrrrrrrrrrrrrst', 'abcdefghijklmnopkrrrrrrrrrrrrrrrrrst'))
delta3 = time.time() - start3

print('1的时间：{:.15f}'.format(delta1))
print('2的时间：{:.15f}'.format(delta2))
print('3的时间：{:.15f}'.format(delta3))
